package leetcodev1.链表;

public class LeetCode61 {

    //将当前最后一个元素 头插一次即旋转一次
    //步骤
    //1.获取链表长度
    //2.将n=k%length 避免k>length
    //3.将倒数第n个节点头插到开头
    public ListNode rotateRight(ListNode head, int k) {
        //异常处理
        if (k == 0 || head == null || head.next == null) {
            return head;
        }

        ListNode index = head, tail = head;
        int length = 0;
        while (index != null) {
            if (index.next == null) {
                tail = index;
            }
            length++;
            index = index.next;
        }

        int n = k % length;
        if (n == 0) {
            return head;
        }

        ListNode quickIndex = head, slowIndex = head, pre = head;
        for (int i = 0; i < n; i++) {
            quickIndex = quickIndex.next;
        }
        while (quickIndex != null) {
            pre = slowIndex;
            quickIndex = quickIndex.next;
            slowIndex = slowIndex.next;
        }
        pre.next = null;
        tail.next = head;
        return slowIndex;
    }
}

class Answer61 {
    //关键点
    //1.倒数第k个 也是正数的n-k个
    //2.构造成循环链表
    public ListNode rotateRight(ListNode head, int k) {
        if (k == 0 || head == null || head.next == null) {
            return head;
        }
        int n = 1;
        ListNode iter = head;
        while (iter.next != null) {
            iter = iter.next;
            n++;
        }
        int add = n - k % n;//将倒数位置转换成正数的
        if (add == n) {
            return head;
        }
        iter.next = head;//转换成循环链表
        while (add-- > 0) {
            iter = iter.next;
        }
        //找到第k个元素
        ListNode ret = iter.next;//答案
        iter.next = null;//将循环链表打破
        return ret;
    }
}
